package com.mgq.algorithm.twotree;

import java.util.ArrayList;
import java.util.LinkedList;
import java.util.List;
import java.util.Queue;

/**
 * @author MaGuangQi
 * @description https://leetcode-cn.com/problems/binary-tree-level-order-traversal/
 * 第102题
 * 给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
 * 3
 * / \
 * 9  20
 * /  \
 * 15   7
 * 结果[[3],[9,20],[15,7]]
 * @date 2020-07-06 23:38
 **/
public class LevelOrder102 {

    /**
     * 解法一: 使用BFS,(广度优先遍历) 这道理考察的是BFS的使用
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root == null) {
            return result;
        }
        //Set visited =new HashSet();
        //如果是图的话,需要判断元素是否已经访问过了
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        //队列保存每层的节点
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<>();
            //巧妙的地方,queue的长度恰好是当前层元素的个数
            int levelSize = queue.size();
            for (int i = 0; i < levelSize; i++) {
                //循环取出当前层元素,放到list中
                TreeNode curNode = queue.poll();
                level.add(curNode.val);
                if (curNode.left != null) {
                    queue.add(curNode.left);
                }
                if (curNode.right != null) {
                    queue.add(curNode.right);
                }
            }
            //把当前层的元素加入
            result.add(level);
        }
        return result;
    }

    /**
     * 解法二: 这道题其实也可以使用DFS来解决.
     * 深度优先遍历
     * 3
     * / \
     * 9  20
     * /  \
     * 15   7
     * 结果[[3],[9,20],[15,7]]
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {

        if (root == null) {
            return result2;
        }
        dfs(root,0);
        return result2;
    }

    /**
     * 全局属性
     */
    private List<List<Integer>> result2 = new ArrayList<>();

    /**
     * 递归的形式(深度优先遍历)
     * 二维数组结果中,假设有3层,那么二维数组的长度就是3.
     * 在每次遍历的时候,当前level恰好是数组的长度
     * 例如: 当前第一层, 结果是[[3]],list长度是1
     * 第二层,结果是[[3],[9,20]]
     * <p>
     * 每次遍历的时候,先放一个level空数组,然后把数组值填满
     * <p>
     * 函数作用,深度优先遍历,遍历node
     *
     * 递归前序遍历 根->左->右
     *
     */
    public void dfs(TreeNode node, int level) {
        if (node == null) {
            return;
        }
        //巧妙的地方, 这里是先创建一个空list,然后再把当前值加入
        if (result2.size() < level + 1) {
            //先初始化一个空数组
            List<Integer> curNode = new ArrayList<>();
            result2.add(curNode);
        }
        //将当前节点值加入list
        result2.get(level).add(node.val);
        dfs(node.left, level + 1);
        dfs(node.right, level + 1);
    }

    /**
     * @author MaGuangQi
     * @description: leetcode 236题 给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
     * https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-tree/
     * @date 2020-06-29 22:08
     **/
    public static class LowestCommonAncestor {
        /**
        *使用递归的三部曲
         * 1.找递归的终止条件
         * 2.找返回值,返回给上层的值
         * 3.单次的过程,(只考虑当前的过程)
         *
         *         3
         *        / \
         *       5   1
         *      / \  / \
         *     6  2  0  8
         *       / \
         *      7   4
         *
         * 注意看结果:
         *LCA(3,1)结果为3   情况一
         *LCA(1,3)结果为3  说明只要其中一个节点和根相等,那个根就是他们的公共祖先
         *LCA(5,1)结果为3 分部在3的左右子树中
         *LCA(6,8)结果为3 分部在3的左右子树中
         *LCA(8,7) = 3　　//分布在3的左右子树中　
         *LCA(6,4) = 5   　 //分布在5的左右子树中
         *LCA(5,2) = 5　    //其中一个节点与5相等
         *
         * 以某个节点为根节点,如果两个指定节点分别在根节点的两侧,那个次根节点就是他们的最近公共祖先
         * 如果两个指定节点在根节点的一端,说明当前根节点不是解,但是解肯定在它的某一端包含解,某一端不包含解
         *
         *如果root为空,或者root==p或者root==q,直接返回root,对应情况一
         *
         * 如果没有情况一返回,说明root不为空,并且root不等于p,也不等于q
         *   分以下情况
         *  一: 一个节点分布在root的左子树,一个分布在root的右子树
         *  二: 两个节点都位于root的左子树
         *  三: 两个节点都位于root的右子树
         *
         *  分别对左右子树进行递归.左右节点分别成为新root节点.(记为新root节点)
         *
         *  两个子树的返回值left和right有不同的情况
         *   一:left和right都不为空,对应情况一
         *   二:left为空,right不为空,对应情况三 两个节点都位于root的右子树
         *   三:left不为空,right为空,对应情况二 两个节点都位于root的左子树
         *
        */
        public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
            if (root == null) {
                System.out.println("root是:null" + " p是:" + p.val + " q是:" + q.val);
            } else {
                System.out.println("root是:"+root.val+" p是:"+p.val+" q是:"+q.val);
            }

            if (root == null || root == p || root == q) {
                return root;
            }
            TreeNode left = lowestCommonAncestor(root.left, p, q);
            TreeNode right = lowestCommonAncestor(root.right, p, q);
            if (left != null && right != null) { //情况一
                return root;
            }
            if (left != null) {   //情况二
                return left;
            }
            return right; //情况三
        }

        public static void main(String[] args) {
            LowestCommonAncestor l = new LowestCommonAncestor();
            TreeNode treeNode=new TreeNode(3);
            TreeNode treeNode1=new TreeNode(5);
            TreeNode treeNode2=new TreeNode(1);
            TreeNode treeNode3=new TreeNode(6);
            TreeNode treeNode4=new TreeNode(2);
            TreeNode treeNode5=new TreeNode(0);
            TreeNode treeNode6=new TreeNode(8);
            TreeNode treeNode7=new TreeNode(7);
            TreeNode treeNode8=new TreeNode(4);
            treeNode4.left=treeNode7;
            treeNode4.right=treeNode8;
            treeNode1.left=treeNode3;
            treeNode1.right=treeNode4;
            treeNode2.left=treeNode5;
            treeNode2.right=treeNode6;
            treeNode.left=treeNode1;
            treeNode.right=treeNode2;
            TreeNode treeNode9 = l.lowestCommonAncestor(treeNode, treeNode, treeNode2);
            System.out.println("最终结果"+treeNode9.val);
        }



        static class TreeNode {
            int val;
            TreeNode left;
            TreeNode right;

            TreeNode(int x) {
                val = x;
            }
        }
    }
}
